package com.ryujung.linked_list.leetCode_23;

import java.util.*;

/*
 * @lc app=leetcode.cn id=23 lang=java
 *
 * [23] 合并K个排序链表
 *
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/description/
 *
 * algorithms
 * Hard (50.06%)
 * Likes:    640
 * Dislikes: 0
 * Total Accepted:    115.6K
 * Total Submissions: 224.9K
 * Testcase Example:  '[[1,4,5],[1,3,4],[2,6]]'
 *
 * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
 * 
 * 示例:
 * 
 * 输入:
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 输出: 1->1->2->3->4->4->5->6
 * 
 */

// @lc code=start
//Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

/**
 * 思路：
 * 遍历数组中所有的节点，将每个节点放入一个可以排序的队列，
 * 创建一个新的链表，新建一个标记头部Node，将队列中最小的取出放入新链表中
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;

        //创建一个可以定义比较规则的优先级队列
        PriorityQueue<ListNode> queue = 
        new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                if (o1.val > o2.val)
                    return 1;
                if (o1.val < o2.val)
                    return -1;
                return 0;

            }
        });
        //将数组放入优先队列中
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null)
                queue.add(lists[i]);
        }

        ListNode res = new ListNode(0), pos = res;
        while (!queue.isEmpty()) {
            pos.next = queue.poll();
            pos = pos.next;
            if (pos.next != null)
                queue.add(pos.next);
        }
        return res.next;
    }

    /**
     * 2023年01月31日15:21:51追加
     * 思路：
     * 暴力将所有值取出来，然后进行排序，在组成新的链表
     */
    public ListNode mergeKLists0(ListNode[] lists) {
        if (lists == null) return null;

        List<Integer> list = new ArrayList<>();
        for (ListNode node : lists) {
            while (node != null) {
                list.add(node.val);
                node = node.next;
            }
        }
        Collections.sort(list);

        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        for (Integer i : list) {
            ListNode newNode = new ListNode(i);
            cur.next = newNode;
            cur = cur.next;
        }
        return pre.next;
    }
    // 时间复杂度：O(n) 需要遍历所有的链表元素
    // 空间复杂度：O(n) 需要额外的list存储所有链表的值

    /**
     * 思路2：
     * 在原有的链表上直接进行拆解和拼接，
     * 将问题细分为合并两个升序链表，然后再依次将所有的链表两两合并
     * 注意：
     * 可以将两个链表合成一个，然后依次用合成好的链表去合并其他链表
     * 也可以将所有链表两两合并，然后再逐渐全部合并
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        int length = lists.length;

        ListNode result = null;
        for (int i = 0; i < length; i++) {
            result = mergeTwoList(result, lists[i]);
        }
        return result;
    }

    public ListNode mergeTwoList(ListNode node1, ListNode node2) {
        if (node1 == null) return node2;
        if (node2 == null) return node1;

        ListNode pre = new ListNode(0);

        ListNode cur = pre;
        ListNode rest1 = node1;
        ListNode rest2 = node2;

        while (rest1 != null || rest2 != null) {
            if (rest1 == null) {
                cur.next = rest2;
                break;
            }
            if (rest2 == null) {
                cur.next = rest1;
                break;
            }

            if (rest1.val <= rest2.val) {
                cur.next = rest1;
                rest1 = rest1.next;
            } else {
                cur.next = rest2;
                rest2 = rest2.next;
            }
            cur = cur.next;
        }

        return pre.next;
    }
    // 时间复杂度：假设每个链表的最长长度是 nn。在第一次合并后，
    // ans 的长度为 n；第二次合并后，ans 的长度为 2×n，第 i 次合并后，
    // ans 的长度为 i×n。第 i 次合并的时间代价
    // 是 O(n+(i−1)×n)=O(i×n)O(n+(i−1)×n)=O(i×n)，
    // 那么总的时间代价为 O(∑i=1~k(i×n))=O((1+k)⋅k2×n)=
    // O(k2n)O(∑i=1~k(i×n))=O((1+k)⋅k/2×n)=O(k^2*n)，
    // 故渐进时间复杂度为 O(k2n)O(k2n)。
    // 空间复杂度：O(1) 固定数量的临时变量

    /**
     * 思路3：
     * 通过优化两个链表合并的方式，将lists中的所有链表进行两两合并，
     * 最后逐渐合并为一条链表，实现分而治之（分治算法）
     * <p>
     * 步骤：
     * 1.使用两个指针，分别从lists的头部和尾部取出一个链表进行合并，
     * 2.再将合并的结果进行递归处理
     * <p>
     * 注意：
     * 使用分治算法常用的方法：
     * 将需要处理的集合，以及处理的范围单独写成方法，进行递归调用
     */
    public ListNode mergeKLists3(ListNode[] lists) {
        return method(lists, 0, lists.length - 1);
    }

    // 分治链表进行两两合并的递归方法
    public ListNode method(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        if (left > right) return null;
        int mid = (left + right) >> 1;
        return mergeTwoList(method(lists, left, mid),
                method(lists, mid + 1, right));

    }
    // 时间复杂度：考虑递归「向上回升」的过程——
    // 第一轮合并k/2 组链表，每一组的时间代价是 O(2n)；
    // 第二轮合并 k/4 组链表，每一组的时间代价是 O(4n)......
    // 所以总的时间代价是
    // O(∑i=1~∞ k/(2^i)×(2^i)*n)=O(kn×logk)，
    // 故渐进时间复杂度为 O(kn×logk)。
    // 空间复杂度：递归会使用到O(logk)空间代价的栈空间。
}
// @lc code=end
